
package leetcode;

//可以使用此方法测试自己的idea编码格式["MyLinkedList","addAtHead","get","addAtHead","addAtHead","deleteAtIndex","addAtHead",
// "get","get","get","addAtHead","deleteAtIndex"]
//[[],                                            [4],[1],[1],[5],[3],[7],[3],[3],[3],[1],[4]]
import java.lang.invoke.VarHandle;
import java.nio.charset.Charset;
import java.util.*;

public class leetcode1 {
    public static void main(String[] args) {
//        int x=5;
//        x=x/10;
//        System.out.print(x);
           leetcode1 l1=new leetcode1();
        //     String s =
        //             "AB";
        //    l1.convert(s,1);

        int []nums ={3,2,1,5,6,4};
        l1.findKthLargest(nums,2);
////        System.out.print(q);
//        int[] nums=new int[]{2,3,6,7};
//        int target=7;
//        List<List<Integer>> s=l1.combinationSum(nums,target);
//        LinkedList<String> strings = new LinkedList<>();

    }
    public TreeNode lowestCommonAncestor2(TreeNode root, TreeNode p, TreeNode q) {
        if(root==null) return null;
        if(root==p||root==q)return root;
        TreeNode left=lowestCommonAncestor2(root.left,p,q);
        TreeNode right=lowestCommonAncestor2(root.right,p,q);
        if(right==null&&left==null) return root;
        if(right==null&&left!=null) return left;
        if(right!=null&&left==null) return right;
        return null;


    }


    public boolean isPalindrome(ListNode head) {
        ListNode mid=isPalindromemid(head);
        ListNode new1=isPalindromererver(mid);
        while(head!=mid){
            if(head.val!=new1.val){
                return false;
            }
            head=head.next;
            new1=new1.next;
        }
        return true;
    }
    public ListNode isPalindromemid(ListNode head) {
        ListNode slow=head;
        ListNode fast=head;
        while(fast.next!=null) {
            slow=slow.next;
            fast=fast.next.next;
        }
        return slow;
    }
    public ListNode isPalindromererver(ListNode head) {
        ListNode pre=null;
        ListNode now=head;
        ListNode next=head.next;
        while (now.next!=null) {
            now.next=pre;
            pre=now;
            now=next;
            next=now.next;
        }
        now.next=pre;
        return now;
    }



    public TreeNode invertTree2(TreeNode root) {
        if(root==null)return root;
        TreeNode temp=root.left;

        root.left=invertTree(root.right);
        root.right=invertTree(temp);
        return root;
    }




    public int findKthLargest(int[] nums, int k) {
        ArrayList arrayList = new ArrayList<Integer>();
        for (int num:nums) {
            arrayList.add(num);
        }
        return findKth(arrayList, k);

    }


    public int maximalSquare(char[][] matrix) {
        int row=matrix.length;
        int column=matrix[0].length;
        int[][] array = new int[row+10][column+10];
        int max=0;

        for (int i=0; i<row; i++){
            for(int j=0; j<column; j++){
                if(matrix[i][j]==0){
                    array[i][j] =0;
                }else {
                    if(i==0||j==0){
                            array[i][j] =1;
                    }else {
                        array[i][j] =Math.min(Math.min(array[i-1][j],array[i][j-1]),array[i-1][j-1])+1;
                    }

                }
                max=Math.max(max,array[i][j]);


            }
        }
        return max*max;
    }

    public  int findKth(List<Integer> list,int k) {
        Random random = new Random();
        int now=list.get(random.nextInt(list.size()));
        ArrayList small = new ArrayList<Integer>();
        ArrayList big = new ArrayList<Integer>();
        ArrayList eq = new ArrayList<Integer>();
        for (int i:list) {
            if(i<now){
                small.add(i);
            }else  if(i>now){
                big.add(i);
            }else{
                eq.add(i);
            }
        }
        if(big.size()>=k){
            return  findKth(big, k);
        }else if (big.size()+ eq.size()<k) {
            return  findKth(small, k-eq.size()-big.size());
        }

        return now;
    }


    public int maxProduct(int[] nums) {
        int ans= Integer.MIN_VALUE;
        int fMax=1,fMin=1;
        for(int num:nums){
            int mx=fMax;
            fMax = Math.max(Math.max(fMax * num, fMin * num), num);
            fMin = Math.min(Math.min(mx * num, fMin * num), num);
            ans = Math.max(ans, fMax);


        }
        return  ans;
    }
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        int[] ints = new int[numCourses];
        Deque<Integer> deque = new ArrayDeque<>();
        List<ArrayList<Integer>> arrayLists = new ArrayList<ArrayList<Integer>>();
        for (int i=0; i<ints.length; i++){
            arrayLists.add(new ArrayList<Integer>());
        }
        for (int[] cur:prerequisites){
            ints[cur[0]]++;
            arrayLists.get(cur[1]).add(cur[0]);
        }
        for (int i=0;i<numCourses;i++){
            if(ints[i]==0)  deque.addLast(i);
        }
        while (!deque.isEmpty()){
            int m=deque.pollFirst();
            numCourses--;
            for(int cur:arrayLists.get(m)){
                ints[cur]--;
                if(ints[cur]==0){
                    deque.addLast(cur);
                }
            }
        }
        return numCourses==0;

    }
    public int numIslands(char[][] grid) {
        int conut =0;
        for(int i=0;i<grid.length;i++){
            for (int j=0;j<grid[0].length;j++){
                if(grid[i][j]=='1'){
                    numIslandsdfs(grid,i,j);
                    conut++;
                }
            }
        }
        return conut;
    }
    public ListNode reverseList(ListNode head) {
        if(head==null) return head;
        ListNode cur= head;
        ListNode pre=null;
        ListNode next=null;
        while (cur.next!=null){
            next=cur.next;
            cur.next=pre;
            pre=cur;
            cur=next;
        }
        cur.next=pre;
        return cur;
    }
    public   void numIslandsdfs(char[][] grid ,int i,int j){
            if(i<0||i>=grid.length||j<0||j>=grid[0].length||grid[i][j]=='0') return;
            grid[i][j]='0';
        numIslandsdfs(grid,i+1,j);
        numIslandsdfs(grid,i-1,j);
        numIslandsdfs(grid,i,j+1);
        numIslandsdfs(grid,i,j-1);
    }

    public int rob(int[] nums) {
        int[] ints = new int[nums.length + 10];


        ints[1]=nums[0];
        for (int i=1;i<nums.length;i++){
            ints[i+1]=Math.max(ints[i],ints[i-1]+nums[i]);
        }
        return  ints[nums.length];
    }


    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        int a=0;
        int b=0;
        ListNode tempa=headA;
        ListNode tempa2=headB;
        while(tempa!=null ){
            tempa=tempa.next;
            a++;
        }
        while(tempa2!=null ){
            tempa2=tempa2.next;
            b++;
        }
        if(a>=b){
            int t=a-b;
            while (t>0){
                headA=headA.next;
                t--;
            }
            while (headA!=headB){
                headA=headA.next;;
                headB=headB.next;
            }
            return headA;
        }else {
            int t=b-a;
            while (t>0){
                headB=headB.next;
                t--;
            }
            while (headA!=headB){
                headA=headA.next;;
                headB=headB.next;
            }
            return headA;
        }

    }
    public ListNode sortList(ListNode head) {
        if(head==null||head.next==null) return head;
        ListNode slow=head;
        ListNode fast=head.next;
        while (fast!=null&&fast.next!=null){
            slow=slow.next;
            fast=fast.next.next;
        }
        ListNode temp=slow.next;
        slow.next=null;
        ListNode left=sortList(head);
        ListNode right=sortList(temp);
        ListNode temp1=new ListNode ();
        ListNode res=temp1;
        while(left!=null&&right!=null){
            if(left.val<right.val){
                temp1.next=left;
                left=left.next;
            }else{
                temp1.next=right;
                right=right.next;
            }
            temp1=temp1.next;

        }
        temp1.next=left!=null?left:right;
        return  res.next;
    }
    public boolean hasCycle(ListNode head) {
        ListNode fast=head;
        ListNode slow=head;

        while (fast!=null&&fast.next!=null&&fast.next.next!=null){
            fast=fast.next.next;
            slow=slow.next;

            if(fast==slow){
                return true;
            }

        }
        return  false;
    }
    public boolean wordBreak(String s, List<String> wordDict) {
        HashSet<String> strings = new HashSet<String>();
        for (String d : wordDict){
            strings.add(d);
        }
        boolean[] dp = new boolean[s.length() + 10];
        dp[0]=true;
        for (int i=1; i<=s.length(); i++) {
            for (int j=1; j<=i&&!dp[i];j++) {
                    String sub=s.substring(j-1,i);
                    if(strings.contains(sub)){
                        dp[i]=dp[j-1];
                    }
            }

        }
        return dp[s.length()];
    }


    public int singleNumber(int[] nums) {
        int m=0;
        for(int num:nums){
            m^=num;
        }
        return m;
    }


    public int longestConsecutive(int[] nums) {
        HashSet<Integer> set = new HashSet<>();
        int maxleng=0;
        for(int num:nums){
            set.add(num);
        }
        for (int num:set){
            int temp=0;
            if(!set.contains(num-1)){
                int cur=num;
                temp=1;
                while (set.contains(cur+1)) {
                    cur++;
                    temp++;
                }
            }
            maxleng=Math.max(maxleng,temp);
        }
        return  maxleng;
    }


        int maxPathSummax=Integer.MIN_VALUE;
    public int maxPathSum(TreeNode root) {
      maxPathSumdp(root);
        return  maxPathSummax;
    }

    public int  maxPathSumdp(TreeNode root) {
        if(root==null){
            return 0;
        }


        int left=maxPathSumdp(root.left);
        int right=maxPathSumdp(root.right);
        maxPathSummax=Math.max(Math.max(left,0)+Math.max(right,0)+root.val, maxPathSummax);
        return Math.max(Math.max(left,right)+root.val,0);
    }


    public int maxProfit(int[] prices) {
            int min=prices[0];
            int max=0;
            for(int i=1;i<prices.length;i++){
                if(prices[i]>=min){
                    max=Math.max(prices[i]-min,max);
                }else {
                    min=prices[i];
                }
            }
            return  max;
    }

    TreeNode flattenroot=null;
    public void flatten(TreeNode root) {
        if(root==null) return;
        flatten(root.right);
        flatten(root.left);
        root.left=null;
        root.right=flattenroot;
        flattenroot=root;
    }


    Map<Integer,Integer>  map=new HashMap<Integer,Integer>();
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        for(int i=0;i<inorder.length;i++){
            map.put(inorder[i],i);
        }
        TreeNode node=findNode( preorder, 0, preorder.length, inorder, 0, inorder.length);
        return node;
    }

    public TreeNode findNode(int[] preorder, int preBegin, int preEnd, int[] inorder, int inBegin, int inEnd) {
        if(preBegin >= preEnd || inBegin >= inEnd){
            return  null;
        }

        int index=map.get(preorder[preBegin]);
        int len=index-inBegin;
        TreeNode root = new TreeNode(inorder[index]);
        root.left=findNode( preorder, preBegin+1,preBegin+len+1, inorder, inBegin,index);
        root.right=findNode( preorder, preBegin+len + 1,preEnd, inorder, index+1,inEnd);

        return  root;


    }

    public int maxDepth(TreeNode root) {

        if(root==null) return 0;
        int left=maxDepth(root.left);
        int right=maxDepth(root.right);
        return Math.max(left,right)+1;

    }

    public List<List<Integer>> levelOrder1(TreeNode root) {
        if(root==null) return  new ArrayList<List<Integer>>();
        Deque<TreeNode> deque = new ArrayDeque<>();
        deque.push(root);
        List<List<Integer>> lists = new ArrayList<List<Integer>>();
        while (!deque.isEmpty()) {
            ArrayList<Integer> list = new ArrayList<>();
            int size=deque.size();
            while(size>0){
                TreeNode temp=deque.pop();
                list.add(temp.val);
                size--;
                if(temp.left!=null) deque.addLast(temp.left);
                if(temp.right!=null) deque.addLast(temp.right);
            }
            lists.add(list);
        }
        return lists;
    }
    public boolean isSymmetric(TreeNode root) {
        return is(root.left,root.right);
    }
    public boolean is(TreeNode left,TreeNode right) {
        if(left==null&&right!=null) return  false;
        if(left!=null&&right==null) return  false;
        if(left==null&&right==null) return  true;
        if(left.val!=right.val) return false;



        return is(left.left,right.right)&&is(left.right,right.left);
    }


       TreeNode temp=new TreeNode();
    public boolean isValidBST1(TreeNode root) {
        if(root==null) return true;
        boolean left=isValidBST1(root.left);
        if (temp!=null&&root.val <=temp.val) return false;
        temp=root;
        boolean right=isValidBST1(root.right);


        return  left&&right;


    }



    public int numTrees(int n) {
        int[][] ints = new int[n + 10][n + 10];
        for(int i=0;i<=n+1;i++){
            for(int j=0;j<=n+1;j++){
                if(i>=j){
                    ints[i][j]=1;
                }
            }
        }
        for (int length=2;length<=n;length++){
            for (int l=1;l+length-1<=n;l++){
                int r=l+length-1;
                for (int i=l;i<=r;i++){
                    ints[l][r]+=ints[l][i-1]*ints[i+1][r];
                }

            }
        }
        return  ints[1][n];


    }



    public List<Integer> inorderTraversal(TreeNode root) {
        ArrayList<Integer> list = new ArrayList<>();
        inorderTraversal11(root,list);
        return list;


    }
    public void inorderTraversal11(TreeNode root,List<Integer> list) {
        if(root==null) return;
        inorderTraversal11(root.left,list);
        list.add(root.val);
        inorderTraversal11(root.right,list);
    }





    public int maximalRectangle(char[][] mat) {
        int n = mat.length, m = mat[0].length, ans = 0;
        int[][] sum = new int[n + 10][m + 10];
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                sum[i][j] = mat[i - 1][j - 1] == '0' ? 0 : sum[i - 1][j] + 1;
            }
        }

        for (int q = 1; q <= n; q++) {
            int [] heights=sum[q];
            int[] l = new int[heights.length];
            Deque<Integer> deque = new ArrayDeque<>();
            for (int i=0;i<heights.length;i++){
                int now=heights[i];
                while (!deque.isEmpty()&&now<=heights[deque.peek()]){
                    deque.pop();
                }
                l[i]=deque.isEmpty()?-1:deque.peek();
                deque.push(i);
            }
            deque.clear();
            int[] r = new int[heights.length];
            for (int i=heights.length-1;i>=0;i--){
                int now=heights[i];
                while (!deque.isEmpty()&&now<=heights[deque.peek()]){
                    deque.pop();
                }
                r[i]=deque.isEmpty()?heights.length:deque.peek();
                deque.push(i);
            }


            for (int i=0;i<heights.length;i++ ){
                int temp=(r[i]-l[i]-1)*heights[i];
                ans=Math.max(temp,ans);

            }
        }
        return ans;
    }




    public int largestRectangleArea(int[] heights) {
        int[] l = new int[heights.length];
        Deque<Integer> deque = new ArrayDeque<>();
        for (int i=0;i<heights.length;i++){
            int now=heights[i];
            while (!deque.isEmpty()&&now<=heights[deque.peek()]){
                deque.pop();
            }
            l[i]=deque.isEmpty()?-1:deque.peek();
            deque.push(i);
        }
        deque.clear();
        int[] r = new int[heights.length];
        for (int i=heights.length-1;i>=0;i--){
            int now=heights[i];
            while (!deque.isEmpty()&&now<=heights[deque.peek()]){
                deque.pop();
            }
            r[i]=deque.isEmpty()?heights.length:deque.peek();
            deque.push(i);
        }

        int ans=0;
        for (int i=0;i<heights.length;i++ ){
            int temp=(r[i]-l[i]-1)*heights[i];
            ans=Math.max(temp,ans);

        }
        return  ans;

    }






    public boolean exist(char[][] board, String word) {
            char[] word1=word.toCharArray();


            for(int i=0;i<board.length;i++){
                for (int j=0;j<board[0].length;j++){
                   if( dfsexist(board,word1,i,j,0)) return true;
                }
            }
            return false;
    }
    public boolean dfsexist(char[][] board, char[] word1,int i, int j,int k) {
        if(i>=board.length||i<0||j>=board[0].length|| j<0 ) return  false;

        if(board[i][j]!=word1[k]) return false;
        if (k == word1.length - 1) return true;
        board[i][j]='0';
        boolean res=(dfsexist(board,word1,i-1,j,k+1)||dfsexist(board,word1,i,j-1,k+1)||dfsexist(board,word1,i+1,j,k+1)
                ||dfsexist(board,word1,i,j+1,k+1));
        board[i][j]=word1[k];
        return res;

    }









    List<List<Integer>> subsetslists = new ArrayList<List<Integer>>();
    List<Integer> subsetslist=new ArrayList<Integer>()  ;
    public List<List<Integer>> subsets(int[] nums) {
        subsetsback(nums,0);

        return subsetslists;
    }
    public void subsetsback(int[] nums,int start) {
            subsetslists.add(new ArrayList<>(subsetslist));
            for (int i=start;i<nums.length;i++){
                subsetslist.add(nums[i]);
                subsetsback(nums,i+1);
                subsetslist.remove(subsetslist.size()-1);
            }
    }


    public void sortColors(int[] nums) {
          int l=0;
          int r=nums.length-1;
          for (int idx=0;idx<=r;){
              if(nums[idx]==0){
                  sortColorswap(nums,idx,l);
                  l++;
                  idx++;
              }else if(nums[idx]==1){
                  idx++;
              }else {
                  sortColorswap(nums,idx,r);
                  r--;
              }
          }
          return ;
    }
    public void sortColorswap(int[] nums,int idx,int x) {
        int temp=nums[idx];
        nums[idx]=nums[x];
        nums[x]=temp;

    }



    public int minDistance(String word1, String word2) {
        int m=word1.length();
        int n=word2.length();
        int[][] dp = new int[m+1][n+1];
        for(int i=0;i<=n;i++){
            dp[0][i] =i;
        }
        for(int i=0;i<=m;i++){
            dp[i][0] =i;
        }
        for (int i=1;i<=m;i++){
            for (int j=1;j<=n;j++){
                if(word1.charAt(i-1)==word2.charAt(j-1)){
                    dp[i][j] =dp[i-1][j-1];
                }else {

                    dp[i][j]=Math.min(Math.min(dp[i-1][j-1],dp[i-1][j]),dp[i][j-1])+1;
                }
            }
        }
        return dp[m][n];
    }
    public int climbStairs(int n) {
        int m1=1;
        int m2=2;
        int sum=1;
        for(int i=3;i<=n;i++){
            sum=m1+m2;
            m1=m2;
            m2=sum;
        }

        return sum;
    }


    public int minPathSum(int[][] grid) {
        int[][] dp = grid;

        for(int i=1; i<grid[0].length; i++){
            dp[0][i] +=dp[0][i-1];
        }
        for(int i=1; i<grid.length; i++){
            dp[i][0] +=dp[i-1][0];
        }
        for (int i=1; i<grid.length; i++){
            for(int j=1; j<grid[0].length; j++){
                dp[i][j] =dp[i][j]+=Math.min(dp[i-1][j],dp[i][j-1]);
            }
        }
        return dp[grid.length-1][grid[0].length-1];
    }
    public int uniquePaths(int m, int n) {
        int[][] dp = new int[m][n];

        for(int i=0; i<n; i++){
            dp[0][i] =1;
        }
        for(int i=1; i<m; i++){
            dp[i][0] =1;
        }
        for (int i=1; i<m; i++){
            for(int j=1; j<n; j++){
                dp[i][j] =dp[i-1][j]+dp[i][j-1];
            }
        }
        return dp[m-1][n-1];
    }


    public int[][] merge(int[][] intervals) {
        Arrays.sort(intervals,(p,q) ->p[0]-q[0]);
        ArrayList<int []> arrays=new ArrayList<int []>();
        for(int[] in :intervals) {
            if(arrays.isEmpty()){
                arrays.add(in);
                }else if(in[0]<=arrays.get(arrays.size()-1)[1]){
                arrays.get(arrays.size()-1)[1]=Math.max(in[1],arrays.get(arrays.size()-1)[1]);
            }else{
                arrays.add(in);
            }
        }
        return arrays.toArray(new int[arrays.size()][]);
    }
    public boolean canJump(int[] nums) {
        boolean[] booleans = new boolean[nums.length];
        booleans[0]=true;

        for(int i=0;i<nums.length;i++){
            if(booleans[i]==false){
                return false;
            }
            for(int j=i+1;j<=i+nums[i]&&j<nums.length;i++){
                booleans[j]=true;
            }
            if(booleans[nums.length-1]==true){
                return  true;
            }
        }
        return true;
    }
    public int maxSubArray(int[] nums) {
        if(nums.length==1){
            return nums[0];
        }
        int[] dp = nums;
       int max=nums[0];
        for(int i=1;i<nums.length;i++){
            if(dp[i-1]<=0){
                max=Math.max(dp[i],max);
                continue;
            }else{
                dp[i]=dp[i-1]+nums[i];
                max=Math.max(dp[i],max);
            }
        }
        return max;
    }
    public List<List<String>> groupAnagrams(String[] strs) {
        HashMap<String, List<String>> stringListHashMap = new HashMap<>();
        for(String str : strs){
            char[] c = str.toCharArray();
            Arrays.sort(c);
            List<String> list = stringListHashMap.getOrDefault(c.toString(),new ArrayList<String>()) ;
            list.add(str);
            stringListHashMap.put(c.toString(),list);
        }
        return new ArrayList<>(stringListHashMap.values());


    }
    List<List<Integer>> permuteresult = new LinkedList<>();
    public List<List<Integer>> permute(int[] nums) {
        int[] is=new int[nums.length];
        back(nums,is,new ArrayList<>());
        return permuteresult;
    }

    public void back(int[] nums,int[] is,List<Integer> temp) {
        if(temp.size()==nums.length){
            permuteresult.add(new ArrayList<>(temp));
            return;
        }
        for(int i=0;i<nums.length;i++){
            if(is[i]==1){
                continue;
            }
            is[i]=1;
            temp.add(nums[i]);
            back(nums,is,temp);
            temp.remove(temp.size()-1);
            is[i]=0;
        }
    }


    public int trap(int[] height) {
        int n=height.length;
        if(n<=2)return 0;
        int ans=0;
        Stack<Integer> stack = new Stack<>();
        stack.push(0);
        for(int i=1;i<n;i++){
          int  mid=stack.peek();
          if(height[i]<height[mid]){
              stack.push(i);
          }
          else {
              while(!stack.isEmpty()&&height[stack.peek()]<height[i]){
                  int curheight=height[stack.pop()];
                  if(!stack.isEmpty()){
                      int w=i-stack.peek()-1;
                      int h=Math.min(height[i],height[stack.peek()])-curheight;
                      ans=ans+w*h;
                  }


              }
          }
          stack.push(i);
        }

    return  ans;
    }


    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> res = new ArrayList<>();
        Arrays.sort(candidates); // 先进行排序
        combinationSumbacktracking(res, new ArrayList<>(), candidates, target, 0);
        return res;
    }

    public void combinationSumbacktracking(List<List<Integer>> res,List<Integer> temp,int[] candidates, int target,int start) {
        if(target==0){
            res.add(new ArrayList<Integer>(temp));
            return;
        }
        for(int i=start;i<candidates.length;i++){
            if (target<candidates[i]){
                return;
            }
            temp.add(candidates[i]);
            combinationSumbacktracking(res, temp, candidates, target-candidates[i], i);
            temp.remove(temp.size()-1);



        }


    }





    public int[] searchRange(int[] nums, int target) {
        int n=nums.length;
        int first=-1;
        int last=-1;
        int l=0;
        int r=n-1;
        while(l<=r){
            int middle=l+(r-l)/2;
            if(nums[middle]==target){
                first=middle;
                r=middle-1;
            }else if(middle<target){
                l=middle+1;
            }else {
                r=middle-1;
            }
        }
        if(first==-1){
            return new int[]{-1,-1};
        }
        l=0;
        r=n-1;
        while(l<=r){
            int middle=l+(r-l)/2;
            if(nums[middle]==target){
                last=middle;
                l=middle+1;
            }else if(middle<target){
                l=middle+1;
            }else {
                r=middle-1;
            }
        }

        return new int[]{first, last};

    }
    public int search(int[] nums, int target) {
        int n=nums.length;
        if(n==0){
            return -1;
        }
        if(n==1){
            if(nums[0]==target){
                return 0;
            }else {
                return -1;
            }
        }
        int l=0;
        int r=n-1;
        while(l<=r){
            int mid=(l+r)/2;
            if(target==nums[mid]){
                return mid;
            }
            if(nums[l]<nums[mid-1]){
                if(target>nums[l]&&target<nums[mid-1]){
                    r=mid-1;
                }else {
                    l=mid+1;
                }
            }
            if(nums[mid+1]<nums[r]){
                if(target>nums[mid+1]&&target<nums[r]){
                    l=mid+1;
                }else {
                    l=mid-1;
                }
            }
        }
        return  -1;

    }
    public int longestValidParentheses(String s) {
        int max=0;
        int[] dp = new int[s.length()];
        for(int i=1;i<s.length();i++){
            if(s.charAt(i)==')'){
                if(s.charAt(i-1)=='('){
                    dp[i] =(i>=2?dp[i-2]:0)+2;


                }else if(i-dp[i-1]>0 && s.charAt(i-dp[i-1]-1)=='('){
                    dp[i] =dp[i-1]+(i-dp[i-1])>=2?dp[i-dp[i-1]-2]:0+2;
                }
            }
            max=Math.max(max,dp[i]);
        }
        return max;
    }



    public void nextPermutation(int[] nums) {
        for (int i=nums.length-1; i>0;i--){
            if(nums[i-1]<nums[i]){
                int x=nums[i];
                nums[i]=nums[i-1];
                nums[i-1]=x;
                return;
            }
        }
    }



    int generateParenthesis_n;
    List<String> generateParenthesis_l1=new ArrayList<String>();
    char[] generateParenthesis_path;;
    public List<String> generateParenthesis(int n) {
        this.generateParenthesis_n=n;
        generateParenthesis_path=new char[generateParenthesis_n * 2];
        generateParenthesis_dfs(0,0);
        return generateParenthesis_l1;
    }
    public void generateParenthesis_dfs(int i, int open) {
        if(i==2*generateParenthesis_n){
            generateParenthesis_l1.add(new String(generateParenthesis_path));
            return;
        }
        if(open<generateParenthesis_n){
            generateParenthesis_path[i]='(';
            generateParenthesis_dfs(i+1,open+1);
        }
        if(i-open<open){
            generateParenthesis_path[i]=')';
            generateParenthesis_dfs(i+1,open);
        }

    }

    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        if(list1==null){
            return list2;
        }
        if(list2==null){
            return list1;
        }
        if(list1.val>=list2.val){
            list2.next=mergeTwoLists(list1,list2.next);
            return list2;
        }
        if(list1.val<list2.val){
            list1.next=mergeTwoLists(list1.next,list2);
            return list1;
        }
        return  new ListNode();
    }
    public boolean isValid(String s) {
        Stack<Character> sta=new Stack<Character>();
        HashMap<Character,Character> map=new HashMap<Character,Character>();
        map.put('{','}');
        map.put('[',']');
        map.put('?','?');
        map.put('(',')');
//        sta.push('?');
        for(int i=0;i<s.length();i++){
            if(s.charAt(i)=='{'||s.charAt(i)=='['||s.charAt(i)=='('){
                sta.push(s.charAt(i));
                continue;
            }else{
                char c=sta.pop();
                if(map.get(c)!=s.charAt(i)){
                    return false;
                }
            }


        }
        if(sta.size()==0){
            return  true;
        }
        return  false;
    }
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummy=new ListNode();
        dummy.next=head;
        ListNode fast=head;
        ListNode slow=head;
        for (int i=1; i<=n; i++){
            fast=fast.next;
        }
        while (fast.next!=null){
            fast=fast.next;
            slow=slow.next;
        }
        slow.next=fast;
        return dummy.next;
    }


    public List<List<Integer>> threeSum1(int[] nums) {
        ArrayList<List<Integer>> lists = new ArrayList<List<Integer>>();
        Arrays.sort(nums);
        for (int i=0; i<nums.length; i++) {
            if(nums[0]>0){
                return lists;
            }
            if(i>0&&nums[i]==nums[i-1]){
                continue;
            }
            int left=i+1;
            int right=nums.length-1;
            while(left<right){
                int s=nums[left]+nums[right]+nums[i];
                if(s==0){
                    lists.add(Arrays.asList(nums[left],nums[right],nums[i]));
                    while (left+1<=right&&nums[left]==nums[left+1]){
                        left++;
                    }
                    while (right-1>=left&&nums[right]==nums[right-1]){
                        right--;
                    }
                    left++;
                    right--;
                }
                else if(s>0){
                    while (right-1>=left&&nums[right]==nums[right-1]){
                        right--;
                    }
                    right--;
                }else {
                    while (left+1<=right&&nums[left]==nums[left+1]){
                        left++;
                    }
                    left++;
                }
            }


        }
        return lists;

    }

    List<String> letterCombinations=new ArrayList<String>();
    StringBuilder letterCombinationstemp=new StringBuilder();


    public List<String> letterCombinations(String digits) {
        if(digits.length()==0){
            return letterCombinations;
        }
        String[] numString = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
        letterCombinationsbackTracking(digits,numString,0);
        return letterCombinations;
    }

    public void letterCombinationsbackTracking(String digits, String[] numString, int num) {
        if(num==digits.length()){
            letterCombinations.add(letterCombinationstemp.toString());
            return;
        }
        String str=numString[digits.charAt(num)-'0'];
        for(int i=0;i<str.length();i++){
            letterCombinationstemp.append(str.charAt(i));
            letterCombinationsbackTracking(digits,numString,num+1);
            letterCombinationstemp.deleteCharAt(letterCombinationstemp.length()-1);
        }
    }


    public int maxArea(int[] height) {
        int length=height.length;
        int left=0;
        int right=length-1;
        int re=0;

        while(left<right){
            int max=Math.min(height[left],height[right])*(right-left);
            re=Math.max(re,max);
            if(height[left]>=height[right]){
                right--;
            }else {
                left++;
            }

        }
        return re;
    }


    public String longestPalindrome1(String s) {
        if(s.length()<2){
            return s;
        }
        boolean[][] p=new boolean[s.length()][s.length()];
        for(int i=0;i<s.length();i++){
            p[i][i]=true;
        }
        int begin=0;
        int maxlength=1;
        for(int L=2;L<=s.length();L++){
            for (int i=0;i<s.length();i++){
                int l=i+L-1;
                if(l>=s.length()){
                    break;
                }

                if(s.charAt(i)==s.charAt(l)){
                    if(l-i<2){
                        p[i][l]=true;
                    }else {
                        p[i][l]=p[i+1][l-1];
                    }
                    if(p[i][l]==true&&l-i+1>maxlength){
                        begin=i;
                        maxlength=l-i+1;
                    }
                }

            }
        }
        return s.substring(begin,begin+maxlength);

    }
    public int lengthOfLongestSubstring1(String s) {
        HashSet hashSet1 = new HashSet();
        char[] chars =s.toCharArray();
        int left=0;
        int right=0;
        int length=0;
        while (right<chars.length) {
            if (hashSet1.add(chars[right])){
                right++;
                length=Math.max(length,right-left);
            }else {
                hashSet1.remove(chars[left]);
                left++;
            }
        }
        return length;
    }
    public ListNode addTwoNumbers1(ListNode l1, ListNode l2) {

        ListNode pre = new ListNode(0);
        ListNode cur=pre;
        int carry=0;

        while (l1!=null ||l2!=null) {
            int a= l1==null? 0:l1.val;
            int b= l2==null? 0:l2.val;
            int sum=a+b+carry;
            carry=sum/10;
            int now=sum%10;
            cur.next=new ListNode(now);
            if(l1!=null){
                l1=l1.next;
            }
            if(l2!=null){
                l2=l2.next;
            }
            cur=cur.next;

        }
        if(carry==1){
            cur.next=new ListNode(1);
        }
        return pre.next;
    }
    public int[] twoSum1(int[] nums, int target) {
        HashMap<Integer, Integer> map = new HashMap<>();
        for(int i=0; i<nums.length; i++){
            map.put(nums[i],i);

        }
        for(int i=0;i<nums.length;i++){
            if(map.containsKey(target-nums[i])){
                if(map.get(target-nums[i])!=i){
                    return new int[] {i,map.get(target-nums[i])};
                }

            }
        }
        return new int[0];
    }





    public String convert(String s, int numRows) {
        if(numRows<2)return s;
        ArrayList<StringBuilder> list = new ArrayList<StringBuilder>();
        for(int i=0; i<numRows; i++) {
            list.add(new StringBuilder());
        }
        int i=0;
        int flag = -1;
        for(char c:s.toCharArray()){
            if(i==0||i==numRows-1)flag=-flag;
            list.get(i).append(c);
            i+=flag;
        }
        StringBuilder c=new StringBuilder();
        for(int j=0; j<numRows; j++){
            c.append(list.get(j));
        }
        return c.toString();
    }


    public String longestPalindrome(String s) {
        int len=s.length();
        int maxlen=0,begin=0;

        boolean[][] p = new boolean[len+1][len+1];

        for(int i=len-1; i>=0; i--){
            for(int j=i; j<=len-1;j++) {
                if(s.charAt(i)==s.charAt(j)){
                    if(j-i<=1){


                        p[i][j]=true;
                    }
                    else{
                        p[i][j]=p[i+1][j-1];
                    }
                    if(p[i][j]==true&&j-i+1>maxlen){
                        begin=i;
                        maxlen=j-i+1;
                    }
                }
            }
        }
        return s.substring(begin, begin+maxlen);
    }
    public int lengthOfLongestSubstring(String s) {
        Set<Character> set = new HashSet<Character>();
        int j=0;
        int i=0;
        int len=0;
        for (i=0; i<s.length()&&j<s.length(); i++){
            if (i!=0){
                set.remove(s.charAt(i-1));
            }
            while (j<s.length()&&!set.contains(s.charAt(j))){
                set.add(s.charAt(j));
                j++;
            }
            len=Math.max(len,j-i);

        }
        return len;
    }


    public  int[] twoSum(int[] nums, int target) {
        int[] result=new int[2];
        for(int i=0; i<nums.length; i++){
            for(int j=i+1; j<nums.length; j++){
                if(nums[j]+nums[i]==target){
                    result[0]=i;
                    result[1]=j;
                    return result;
                }
            }
        }
        return result;
    }

    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode head = null;
        ListNode tail =null;
        int carry=0;
        while(l1!=null ||l2!=null){
            int n1= l1==null? 0:l1.val;
            int n2= l2==null? 0:l2.val;
            int sum=n1+n2+carry;
            if(head==null){
                head=tail=new ListNode(sum%10);
            }
            else{
                tail.next=new ListNode(sum%10);
                tail=tail.next;
            }
            carry=sum/10;
            if(l1!=null){
                l1=l1.next;
            }
            if(l2!=null){
                l2=l2.next;
            }
        }
        if(carry!=0){
            tail.next=new ListNode(1);
        }
        return head;
    }
    public boolean containsDuplicate(int[] nums) {
        Set<Integer> set = new HashSet<Integer>();
        for (int num: nums) {
            if (!set.add(num)) return true;
        }
        return false;

    }
    public boolean containsNearbyDuplicate(int[] nums, int k) {

        Map<Integer, Integer> map = new HashMap<Integer, Integer>();
        for (int n=0; n < nums.length; n++) {

            if (map.containsKey(nums[n])) {

                if(Math.abs(map.get(nums[n])-n)<=k){
                    return true;
                }
                else {
                    map.replace(nums[n],n);
                }
            }else {
                map.put(nums[n],n);
            }
        }
        return false;

    }
    public TreeNode invertTree(TreeNode root) {
        if(root==null) return root;
        TreeNode temp=root.left;
        root.left=root.right;
        root.right=temp;
        root.left=invertTree(root.left);
        root.right=invertTree(root.right);
        return root;
    }
    public static List<String> summaryRanges(int[] nums) {
        int i=0;
        List<String> ret = new ArrayList<String>();
        while(i<nums.length){
            int low=i;
            i++;
            while(i<nums.length&&nums[i]==nums[i-1]+1){
                i++;
            }
            StringBuffer stringBuffer = new StringBuffer();
            stringBuffer.append(nums[low]);
            int high=i-1;
            if(low<high){
                stringBuffer.append("->");
                stringBuffer.append(high);
            }
            ret.add(stringBuffer.toString());
        }
        return ret;
    }

    public int minSubArrayLen(int target, int[] nums) {
        int fast;
        int sum=0;
        int slow=0;
        int size=Integer.MAX_VALUE;
        for(fast=0;fast<nums.length;fast++){
            sum+=nums[fast];
            while(sum>=target){
                size=Math.min(fast-slow+1,size);
                sum-=nums[slow];
                slow++;
            }
        }
        return size;
    }
    public static  int[][] generateMatrix(int n) {
        int[][] ret=new int[n][n];
        int num=1;
        int target=n*n;
        int l=0;
        int r=n-1;
        int b=n-1;
        int t=0;
        while(num<=target){
            for(int i=l;i<=r;i++){
                ret[t][i]=num++;

            }
            t++;
            for(int i=t;i<=b;i++){
                ret[i][r]=num++;

            }
            r--;
            for(int i=r;i>=l;i--){
                ret[b][i]=num++;

            }
            b--;
            for(int i=b;i>=t;i--){
                ret[i][l]=num++;

            }
            l++;
        }
        return ret;
    }
    public ListNode detectCycle(ListNode head) {
        ListNode fast=head;
        ListNode slow=head;
        while(fast!=null&&fast.next!=null){
            fast.next=fast.next.next;
            slow.next=slow.next;
            if(fast==slow){
                ListNode index1=fast;
                ListNode index2=head;
                while (index1!=index2){
                    index1=index1.next;
                    index2=index2.next;
                }
                return index1;
            }

        }
        return  null;
    }
    public boolean isAnagram(String s, String t) {
        int[] ints = new int[26];
        for(int i=0;i<s.length();i++){
            ints[s.charAt(i)-'a']++;
        }
        for(int i=0;i<t.length();i++){
            ints[t.charAt(i)-'a']--;
        }
        for(int i:ints){
            if(i!=0){
                return false;
            }
        }
        return true;
    }
    public int[] intersection(int[] nums1, int[] nums2) {
        Set<Integer> ints = new HashSet<Integer>();
        Set<Integer> ints2 = new HashSet<Integer>();
        int m=0;


        for (int i:nums1){
            ints.add(i);
        }
        for (int i:nums2){
            if(ints.contains(i)){
                ints2.add(i);
            }
        }
        int[] ints1 = new int[ints2.size()];
        for(int i:ints2){
            ints1[m]=i;
            m++;
        }
        return  ints1;
    }
    public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
        int length=nums1.length;
        int count=0;
        HashMap<Integer, Integer> integerIntegerHashMap = new HashMap<>();
        for (int i=0;i<length;i++){
            for(int j=0;j<length;j++){
                int m=nums1[i]+nums2[j];
                if(integerIntegerHashMap.containsKey(m)){
                    integerIntegerHashMap.put(m,integerIntegerHashMap.get(m)+1);
                }
                else{
                    integerIntegerHashMap.put(m,1);
                }
            }

        }
        for(int i=0;i<length;i++){
            for(int j=0;j<length;j++){
                int m=0-(nums3[i]+nums4[j]);
                if(integerIntegerHashMap.containsKey(m)){
                    count+=integerIntegerHashMap.get(m);
                }
            }


        }
        return count;


    }


    public boolean canConstruct(String ransomNote, String magazine) {
        HashMap<Character, Integer> map = new HashMap<>();
        for(int i=0;i<magazine.length();i++){
            char a=magazine.charAt(i);
            if(!map.containsKey(a)){
                map.put(a,1);
            }else{
                map.put(a,map.get(a)+1);
            }
        }
        for(int i=0;i<ransomNote.length();i++){
            char a=ransomNote.charAt(i);
            if(map.containsKey(a)) {
                map.put(a, map.get(a) - 1);
                if(map.get(a) <0){
                    return false;
                }
            }
        }

        return true;
    }

    public List<List<Integer>> threeSum(int[] nums) {
        ArrayList<List<Integer>> lists = new ArrayList<List<Integer>>();
        Arrays.sort(nums);
        for (int i=0;i<nums.length;i++){
            if(nums[i]>0){
                return lists;
            }
            if(i>0&&nums[i]==nums[i-1]){
                continue;
            }
            ArrayList<Integer> list = new ArrayList<>();
            int right=nums.length-1;
            int left=i+1;
            while (left<right){
                int a=nums[left]+nums[right]+nums[i];
                if(a==0){
                    lists.add(Arrays.asList(nums[left],nums[right],nums[i]));
                    while (left<right&&nums[left]==nums[left+1]){
                        left++;
                    }
                    while (left<right&&nums[right]==nums[right-1]){
                        right--;
                    }
                    left++;
                    right--;
                }else if(a>0){
                    right--;
                }else{
                    left++;
                }
            }

        }
        return lists;

    }

    public List<List<Integer>> fourSum(int[] nums, int target) {
        ArrayList<List<Integer>> lists = new ArrayList<>();
        Arrays.sort(nums);
        for(int k=0;k<nums.length;k++){
            if(nums[k]>0&&nums[k]>=target){
                return lists;
             }
            if(k>0&&nums[k]==nums[k-1]){
                continue;
            }
            for (int i=k+1;i<nums.length;i++){
                if(i>k+1&&nums[k]==nums[k-1]){
                    continue;
                }

                ArrayList<Integer> list = new ArrayList<>();
                int right=nums.length-1;
                int left=i+1;
                while (left<right){
                    int a=nums[left]+nums[right]+nums[i]+nums[k];
                    if(a==target){
                        lists.add(Arrays.asList(nums[left],nums[right],nums[i],nums[k]));
                        while (left<right&&nums[left]==nums[left+1]){
                            left++;
                        }
                        while (left<right&&nums[right]==nums[right-1]){
                            right--;
                        }
                        left++;
                        right--;
                    }else if(a>target){
                        right--;
                    }else{
                        left++;
                    }
                }

            }
        }

        return lists;
    }

    public void reverseString(char[] s) {
        if(s==null||s.length==1)return;
        int i=0,j=s.length-1;
        while(i<j){
            char temp=s[i];
            s[i]=s[j];
            s[j]=temp;
            i++;
            j--;
        }

    }
//给定一个字符串 s 和一个整数 k，从字符串开头算起，每计数至 2k 个字符，就反转这 2k 字符中的前 k 个字符。
//
//    如果剩余字符少于 k 个，则将剩余字符全部反转。
//    如果剩余字符小于 2k 但大于或等于 k 个，则反转前 k 个字符，其余字符保持原样。
    public String reverseStr(String s, int k) {
        char[] c =s.toCharArray();

        for(int i = 0; i < c.length;i=i+2*k) {
            int start = i;
            // 判断尾数够不够k个来取决end指针的位置
            int end = Math.min(c.length - 1,start + k - 1);
            while(start < end){

                char temp = c[start];
                c[start] = c[end];
                c[end] = temp;

                start++;
                end--;
            }

        }
        return new String(c);
    }

    public String pathEncryption(String path) {
        StringBuilder builder = new StringBuilder();
        for(int i = 0; i < path.length(); i++) {
            if(path.charAt(i)=='.'){
                builder.append(' ');
            }else{
                builder.append(path.charAt(i));
            }
        }
        return builder.toString();

    }
//    给你一个字符串 s ，请你反转字符串中 单词 的顺序。
//
//    单词 是由非空格字符组成的字符串。s 中使用至少一个空格将字符串中的 单词 分隔开。
//
//    返回 单词 顺序颠倒且 单词 之间用单个空格连接的结果字符串。
//
//    注意：输入字符串 s中可能会存在前导空格、尾随空格或者单词间的多个空格。返回的结果字符串中，单词间应当仅用单个空格分隔，且不包含任何额外的空格。
    public String reverseWords(String s) {
        StringBuilder stringBuilder = new StringBuilder();
        for (int i = 0; i < s.length(); i++) {
            if(s.charAt(i) == ' '){
                continue;
            }else{
                stringBuilder.append(s.charAt(i));
            }
        }
        int length=stringBuilder.length()-1;
        stringBuilder=reverse(stringBuilder,0,length);
        int start=0,end=0;
        for(int i=0;i<=length;i++){
            if(s.charAt(i) != ' '){
                end++;
            }else {
                break;
            }
        }
        while (start<=length){
            stringBuilder=reverse(stringBuilder,start,end);
            start=end+2;
            for(int i=start;i<=length;i++){
                if(s.charAt(i) == ' '){
                    start++;
                }else {
                    break;
                }
            }
            end=start;
            for(int i=end;i<=length;i++){
                if(s.charAt(i) != ' '){
                    end++;
                }else {
                    break;
                }
            }
        }
        return stringBuilder.toString();
    }
    public StringBuilder reverse(StringBuilder s, int start, int end){
        while (start < end) {
            char temp = s.charAt(start);
            s.setCharAt(start, s.charAt(end));
            s.setCharAt(end, temp);
            start++;
            end--;
        }
        s.reverse();
        return  s;

    }

    public boolean repeatedSubstringPattern(String s) {

        int length=s.length();
        if(length<=1)return true;
        int start=0,end=1;
        for(;end<=length-1;){
            if(s.charAt(end)!=s.charAt(start)){
                end++;
            }else {
                end++;
                start++;
            }

        }
        int cha=end-start+1;
        if(cha==length){
            return  false;
        }
        return false;
    }
    public String removeDuplicates(String s) {
        Stack<Character> characters = new Stack<Character>();
        for(int i=s.length()-1;i>=0;i--){
            if(characters.isEmpty()){
                characters.push(s.charAt(i));
            }else {
                if(s.charAt(i)==characters.peek()){
                    characters.pop();
                }else {
                    characters.push(s.charAt(i));
                }
            }
        }
        String str="";
        while (!characters.isEmpty()){
             str+=characters.pop();
        }
        return str;
    }

    public int evalRPN(String[] tokens) {
        LinkedList<Integer> list = new LinkedList<>();
        for(String c:tokens){
            if (c.equals("+")) {
                list.push(list.pop()+list.pop());

            }else if (c.equals("-")){
                int num2=list.pop();
                int num1=list.pop();
                list.push(num1-num2);

            }else if (c.equals("*")){
                list.push(list.pop()*list.pop());

            }else if (c.equals("/")){
                int num2=list.pop();
                int num1=list.pop();
                list.push(num1/num2);

            }else {
                list.push(Integer.valueOf(c));
            }
        }
        return list.pop();
    }

    public static int[] maxSlidingWindow(int[] nums, int k) {
        Deque<Integer> integers = new LinkedList<>();
        int[] ints = new int[nums.length-k+1];

        for (int i=0; i<nums.length;i++){
            if(i<=k-1){
                push1(integers,nums[i]);
            }else {
                pop1(integers,nums[i-k]);
                push1(integers,nums[i]);
            }
            if(i>=k-1){
                ints[i-k+1]=getmax(integers);
            }
        }
        return ints;
    }
    public static void pop1(Deque<Integer> integers, int num){
        if(!integers.isEmpty()&&num==getmax(integers)){
            integers.pollFirst();
        }

    }
    public static void push1(Deque<Integer> integers, int num){
        if(integers.isEmpty()){
            integers.addLast(num);
        }else {
            while (!integers.isEmpty()&&num>integers.peekLast()){
                integers.removeLast();
            }
            integers.addLast(num);
        }

    }
    public static int getmax(Deque<Integer> integers){
        return integers.peekFirst();
    }


    public int[] topKFrequent2(int[] nums, int k) {
        Map<Integer,Integer> map = new HashMap<>();//key为数组元素值,val为对应出现次数
        for(int num:nums){
            map.put(num,map.getOrDefault(num,0)+1);
        }

        //在优先队列中存储二元组(num,cnt),cnt表示元素值num在数组中的出现次数
        //出现次数按从队头到队尾的顺序是从小到大排,出现次数最低的在队头(相当于小顶堆)

        PriorityQueue<int[]> pq = new PriorityQueue<>((pair1,pair2)->pair1[1]-pair2[1]);
        for(Map.Entry<Integer,Integer> entry:map.entrySet()){//小顶堆只需要维持k个元素有序
            if(pq.size()<k){//小顶堆元素个数小于k个时直接加
                pq.add(new int[]{entry.getKey(),entry.getValue()});
            }else{
                if(entry.getValue()>pq.peek()[1]){//当前元素出现次数大于小顶堆的根结点(这k个元素中出现次数最少的那个)
                    pq.poll();//弹出队头(小顶堆的根结点),即把堆里出现次数最少的那个删除,留下的就是出现次数多的了
                    pq.add(new int[]{entry.getKey(),entry.getValue()});
                }
            }
        }
        int[] ans = new int[k];
        for(int i=k-1;i>=0;i--){//依次弹出小顶堆,先弹出的是堆的根,出现次数少,后面弹出的出现次数多
            ans[i] = pq.poll()[0];
        }
        return ans;
    }
    public List<List<Integer>> levelOrder(TreeNode root) {
        if(root==null) return new LinkedList<List<Integer>>();
        LinkedList<TreeNode> integers = new LinkedList<TreeNode>();
        integers.add(root);
        List<List<Integer>> lists = new LinkedList<List<Integer>>();
        while (!integers.isEmpty()){
            LinkedList<Integer> integers1 = new LinkedList<>();
            int size = integers.size();

            while (size>0){
                TreeNode temp=integers.poll();
                integers1.add(temp.val);
                if(temp.left!=null){
                    integers.add(temp.left);
                }
                if(temp.right!=null){
                    integers.add(temp.right);
                }
                size--;
            }
            lists.add(integers1);
        }
        return lists;
    }

    public List<List<Integer>> levelOrderBottom(TreeNode root) {
        if(root==null){
            return new LinkedList<List<Integer>>();
        }
        LinkedList<TreeNode> treeNodes = new LinkedList<TreeNode>();
        treeNodes.add(root);

        LinkedList<Integer> number = new LinkedList<Integer>();
        LinkedList<List<Integer>> lists = new LinkedList<List<Integer>>();
        while (!treeNodes.isEmpty()){

            int size=treeNodes.size();

            while (size>0){
                TreeNode temp=treeNodes.poll();
                number.add(temp.val);
                if(temp.left!=null){
                    treeNodes.add(temp.left);

                }
                if(temp.right!=null){
                    treeNodes.add(temp.right);

                }
                size--;
            }
            lists.addFirst(number);


        }
        return lists;
    }

    public List<Integer> rightSideView(TreeNode root) {
        if(root==null){
            return new LinkedList<Integer>();
        }
        LinkedList<TreeNode> treeNodes = new LinkedList<TreeNode>();
        treeNodes.add(root);

        LinkedList<Integer> number = new LinkedList<Integer>();

        while (!treeNodes.isEmpty()){

            int size=treeNodes.size();

            while (size>0){
                TreeNode temp=treeNodes.poll();
                if(size==1){
                    number.add(temp.val);
                }

                if(temp.left!=null){
                    treeNodes.add(temp.left);

                }
                if(temp.right!=null){
                    treeNodes.add(temp.right);

                }
                size--;
            }



        }
        return number;
    }


    public List<Double> averageOfLevels(TreeNode root) {
        if(root==null){
            return new LinkedList<Double>();
        }
        LinkedList<TreeNode> treeNodes = new LinkedList<TreeNode>();
        treeNodes.add(root);

        LinkedList<Double> number = new LinkedList<Double>();

        while (!treeNodes.isEmpty()){

            int size=treeNodes.size();
            int current=size;
            double cur=0;
            while (size>0){
                TreeNode temp=treeNodes.poll();
                cur+=temp.val;
                if(temp.left!=null){
                    treeNodes.add(temp.left);

                }
                if(temp.right!=null){
                    treeNodes.add(temp.right);

                }
                size--;
            }
            cur=cur/current;
            number.add(cur);


        }
        return number;
    }

    public List<List<Integer>> levelOrder(Node root) {
        if(root==null) return new LinkedList<List<Integer>>();
        LinkedList<Node> integers = new LinkedList<Node>();
        integers.add(root);
        List<List<Integer>> lists = new LinkedList<List<Integer>>();
        while (!integers.isEmpty()){
            LinkedList<Integer> integers1 = new LinkedList<>();
            int size = integers.size();

            while (size>0){
                Node temp=integers.poll();
                integers1.add(temp.val);
                for(Node temp2 : temp.children){
                    if(temp2!=null){
                        integers.add(temp2);
                    }
                }

                size--;
            }
            lists.add(integers1);
        }
        return lists;
    }

    public List<Integer> largestValues(TreeNode root) {
        if(root==null) return new LinkedList<Integer>();
        LinkedList<TreeNode> integers = new LinkedList<TreeNode>();
        integers.add(root);
        LinkedList<Integer> integers1 = new LinkedList<>();
        while (!integers.isEmpty()){

            int size = integers.size();
            int cur=Integer.MIN_VALUE;
            while (size>0){
                TreeNode temp=integers.poll();
                if(temp.val>cur){
                    cur=temp.val;
                }


                if(temp.left!=null){
                    integers.add(temp.left);
                }
                if(temp.right!=null){
                    integers.add(temp.right);
                }

                size--;
                if(size==0){
                    integers1.add(cur);
                }
            }

        }
        return integers1;
    }

    public Node1 connect(Node1 root) {
        if(root==null) return root;
        LinkedList<Node1> integers = new LinkedList<Node1>();
        integers.add(root);
        LinkedList<Integer> integers1 = new LinkedList<>();
        while (!integers.isEmpty()){

            int size = integers.size();

            while (size>0){
                Node1 temp=integers.poll();
//                if(integers.peek()!=null){
//                    temp.next=integers.peek();
//                }else {
//                    temp.next=null;
//                }
                if(size==1){
                    temp.next=null;
                }else {
                    temp.next=integers.peek();
                }

                if(temp.left!=null){
                    integers.add(temp.left);
                }
                if(temp.right!=null){
                    integers.add(temp.right);
                }


                size--;

            }

        }
        return root;
    }

    public int countNodes(TreeNode root) {
        return count(root)+1;
    }
    public int count(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int m1 = 0;
        int m2=0;
        if (root.left != null) {
            m1 = count(root.left) + 1;
        }
        if (root.left != null) {
             m2 = count(root.right)+1;
        }
        return m1 + m2;
    }

    public List<String> binaryTreePaths(TreeNode root) {

        LinkedList<String> strings = new LinkedList<>();
        LinkedList<Integer> paths = new LinkedList<>();
        binary(root, paths, strings);
        return strings;
    }
    public void binary(TreeNode root,List<Integer> paths,List<String> list) {
        paths.add(root.val);

        if (root.left==null&&root.right==null) {
            StringBuilder sb = new StringBuilder();// StringBuilder用来拼接字符串，速度更快
            for (int i = 0; i < paths.size() - 1; i++) {
                sb.append(paths.get(i)).append("->");
            }
            sb.append(paths.get(paths.size() - 1));// 记录最后一个节点
            list.add(sb.toString());// 收集一个路径
            return;
        }
        if (root.left != null) { // 左
            binary(root.left, paths, list);
            paths.remove(paths.size() - 1);// 回溯
        }
        if (root.right != null) { // 右
            binary(root.right, paths, list);
            paths.remove(paths.size() - 1);// 回溯
        }
        return ;
    }

    int maxdepth =Integer.MIN_VALUE;
    int result;
    public int findBottomLeftValue(TreeNode root) {
        result=root.val;
        LeftValue(root,1);
        return result;
    }
    public void LeftValue(TreeNode root,int depth) {
        if(root.left == null&&root.right == null){
            if(depth >maxdepth){
                maxdepth = depth;
                result=root.val;
            }
        }
        if(root.left!=null){
            LeftValue(root.left,depth+1);
        }
        if(root.right!=null){
            LeftValue(root.right,depth+1);
        }

    }

    public TreeNode searchBST(TreeNode root, int val) {
        if(root.val==val){
            return root;
        }else if(root.val <val){
            searchBST(root.right,val);
        }else {
            searchBST(root.left,val);
        }
        return new TreeNode();

    }
    TreeNode pre =null;
    public boolean isValidBST(TreeNode root) {
        if(root==null){
            return true;
        }
        boolean left =isValidBST(root.left);
        if(pre!=null&&pre.val>root.val){
            return false;
        }
        pre.val=root.val;
        boolean right =isValidBST(root.right);
        return left&&right;
    }
    int min=Integer.MAX_VALUE;
    public int getMinimumDifference(TreeNode root) {
        if(root==null){
            return min;
        }
        getMinimumDifference(root.left);
        if(pre!=null&&root.val<min){
            min=Math.abs(root.val- pre.val);
        }
        pre=root;

        getMinimumDifference(root.right);
        return min;
    }

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root==null){return null;}
        if(root==p||root==q){return root;}
        TreeNode left=lowestCommonAncestor(root.left,p,q);
        TreeNode right=lowestCommonAncestor(root.right,p,q);
        if(left!=null&&right!=null){
            return root;
        }
        if(left!=null){
            return left;
        }
        if(right!=null){
            return right;
        }
        return null;
    }

    public TreeNode lowestCommonAncestor1(TreeNode root, TreeNode p, TreeNode q) {
        if(root==null) return root;
        if(root.val>p.val&&root.val> q.val){
            TreeNode left=lowestCommonAncestor1(root.left,p,q);
            if(left!=null) return left;
        }
        if(root.val<p.val&&root.val< q.val){
            TreeNode right=lowestCommonAncestor1(root.right,p,q);
            if(right!=null) return right;
        }
        return root;
    }

    public TreeNode insertIntoBST(TreeNode root, int val) {
        if(root==null) {
            return new TreeNode(val);
        }
        if(root.val>val){
            root.left=insertIntoBST(root.left,val);
        }
        if(root.val<val){
            root.right=insertIntoBST(root.right,val);
        }

        return root;
    }
}












